class Node{
    constructor(element){
        this.element = element;
        this.left = null;
        this.right = null;
    }   
}

class Tree{
    constructor() {
        this.root = null;
    }

    //插入  左侧子节点比父节点小，右侧子节点比父节点大
    insert(element){
        //1.创建节点
        let node = new Node(element);
        if(this.root === null){
            //树为空
            this.root = node;
        }else{
            this.insertNode(node,this.root);
        }
    }

    insertNode(newNode,rootNode){
        if(newNode.element < rootNode.element){
            //左边
            if(rootNode.left === null){
                rootNode.left = newNode;
            }else{
                this.insertNode(newNode,rootNode.left);
            }
        }else{
            //右边
            if(rootNode.right === null){
                rootNode.right = newNode;
            }else{
                this.insertNode(newNode,rootNode.right);
            }
        }
    }

    //深度
    deep(){
        return this.deepNum(this.root);
    }

    deepNum(node){ 
        //当前节点是null
        if(node === null){
            return 0
        }

        // return 1 + Math.max(左侧子节点的深度,右侧子节点的深度);
        return 1 + Math.max(this.deepNum(node.left),this.deepNum(node.right))
    }
}

let tree = new Tree();

let arr = [15,20,7,null,null,3,9];

arr.forEach(item => {
    if(item != null){
        tree.insert(item);
    }
})

console.log(tree.deep())
